`:top

In `F33f`_`[computer science`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computer_science]`_`f, a `!pointer algorithm`! (sometimes called a pointer machine, or a reference machine; see the article `F33f`_`[Pointer machine`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Pointer_machine]`_`f for a close but non-identical concept) is a type of algorithm that manages a linked data structure. This concept is used as a model for lower-bound proofs and specific restrictions on the linked data structure and on the algorithm's access to the structure vary.

This model has been used extensively with problems related to the `F33f`_`[disjoint-set data structure`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Disjoint-set_data_structure]`_`f. Thus, `F33f`_`[Tarjan`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Robert_Endre_Tarjan]`_`f and La Poutré used this model to prove lower bounds on the amortized complexity of a disjoint-set data structure`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f]`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f] (La Poutré also addressed the interval split-find problem). `F33f`_`[Blum`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Norbert_Blum]`_`f used this model to prove a lower bound on the single operation worst-case time of disjoint set data structure.`:cite-ref-3[`F5bf`_`[3`#cite-note-3]`_`f] Blum and Rochow proved a worst-case lower bound for the interval union-find problem.`:cite-ref-4[`F5bf`_`[4`#cite-note-4]`_`f]

>>Contents

• `F0af`_`[Example`#example]`_`f

• `F0af`_`[References`#references]`_`f

-─

>>Example

In Tarjan's lower bound for the disjoint set union problem, the assumptions on the algorithm are:

• The algorithm maintains a linked structure of nodes.

• Each element of the problem is associated with a node.

• Each set is represented by a node.

• The nodes of each set constitute a distinct connected component in the structure (this property is called `*separability`*).

• The `!find`! operation is performed by following links from the element node to the set node.

Under these assumptions, the lower bound of Ω Ω ( m α α ( m , n ) ) {\\displaystyle \\Omega (m\\alpha (m,n))} on the cost of a sequence of `*m`* operations is proven.

>>References

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `:citereftarjan1979`aTarjan, Robert E. (1979). "A class of algorithms which require nonlinear time to maintain disjoint sets". `*Journal of Computer and Systems Sciences`*. `!18`!: 110–127.

`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f `:citerefla-poutr-1990`aLa Poutré, Johannes A. (1990). "Lower bounds for the union-find and the split-find problem on pointer machines". `*Proc. 22nd Annual ACM Symposium on the Theory of Computing`*. ACM. pp. 34–44.

`:cite-note-3`!3.`! `F0af`_`[↑`#cite-ref-3]`_`f `:citerefblum1986`aBlum, Norbert (1986). "On the single operation worst-case time complexity of the disjoint set union problem". `*SIAM Journal on Computing`*. `!15`!: 1021–1024.

`:cite-note-4`!4.`! `F0af`_`[↑`#cite-ref-4]`_`f `:citerefblumrochow1994`aBlum, Norbert; Rochow, Henning (1994). "A lower bound on the single operation worst-case time complexity of the union-find problem on intervals". `*Information Processing Letters`*. `!51`!: 57–60.

`c`F0af`_`[↑ Back to top`#top]`_`f`a